package BitManipulation;

public class _397_IntegerReplacement {
    public int integerReplacement_1(int n) {
        int count = 0;
        if(n==1) return count;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1;
            } else if (n == 3 || ((n >>> 1) & 1) == 0) {
                --n;
            } else {
                ++n;
            }
            count++;
        }
        return count;
    }

    public int integerReplacement(int n) {
        return (int)integerReplace(n);
    }

    public long integerReplace(long n) {
        if(n==1) return 0;
        return 1+ (n%2==0?integerReplace(n/2):Math.min(integerReplace(n+1),integerReplace(n-1)));
    }
}
